package merge

/*
归并排序（mergesort）是一种基于分治策略的排序算法，包含图11‑10所示的“划分”和“合并”阶段。
1. 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
2. 合并阶段：当子数组长度为1时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较
长的有序数组，直至结束。
*/
type merge struct {
}

/*
合并左子数组和右子数组
數組 左 中 右 下標
*/
func (m merge) merge(nums []int, left, mid, right int) {
	//左子数组区间为[left,mid],右子数组区间为[mid+1,right]
	//创建一个临时数组tmp，用于存放合并后的结果
	tmp := make([]int, right-left+1)
	//初始化左子数组和右子数组的起始索引
	i, j, k := left, mid+1, 0

	//劃分成兩段數組

	//当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
	for i <= mid && j <= right {
		if nums[i] <= nums[j] {
			tmp[k] = nums[i]
			i++
		} else {
			tmp[k] = nums[j]
			j++
		}
		// 填充一個 指針向後移動
		k++
	}
	//将左子数组和右子数组的剩余元素复制到临时数组中
	for i <= mid {
		tmp[k] = nums[i]
		i++
		k++
	}
	for j <= right {
		tmp[k] = nums[j]
		j++
		k++
	}
	//将临时数组tmp中的元素复制回原数组nums的对应区间
	for k := 0; k < len(tmp); k++ {
		nums[left+k] = tmp[k]
	}
}

/*归并排序*/
func (m merge) mergeSort(nums []int, left, right int) {
	//终止条件
	if left >= right {
		return
	}
	//划分阶段
	mid := left + (right-left)/2
	m.mergeSort(nums, left, mid)
	m.mergeSort(nums, mid+1, right)
	//合并阶段
	m.merge(nums, left, mid, right)
}

/*
 11.6.2算法特性
‧时间复杂度为𝑂(𝑛log𝑛)、非自适应排序：划分产生高度为log𝑛的递归树，每层合并的总操作数量
为𝑛，因此总体时间复杂度为𝑂(𝑛log𝑛)。
‧空间复杂度为𝑂(𝑛)、非原地排序：递归深度为log𝑛，使用𝑂(log𝑛)大小的栈帧空间。合并操作需
要借助辅助数组实现，使用𝑂(𝑛)大小的额外空间。
‧稳定排序：在合并过程中，相等元素的次序保持不变
*/

/*
MergeSort 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
*/
func (m merge) MergeSortGo(arr []int) []int {
	var ll = len(arr)
	if ll < 2 {
		return arr
	}
	var middle = ll / 2
	left := arr[0:middle]
	right := arr[middle:]
	return m.mergeGO(m.MergeSortGo(left), m.MergeSortGo(right))
}

func (m merge) mergeGO(left, right []int) []int {
	result := make([]int, 0, len(left)+len(right))
	for len(left) > 0 && len(right) > 0 {
		if left[0] <= right[0] {
			result = append(result, left[0])
			left = left[1:]
		} else {
			result = append(result, right[0])
			right = right[1:]
		}
	}
	for len(left) > 0 {
		result = append(result, left[0])
		left = left[1:]
	}
	for len(right) > 0 {
		result = append(result, right[0])
		right = right[1:]
	}
	return result
}
